<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 最长回文子序列
         * 输入：s = "bbbab"
         * 输出：4 
         * 解释：一个可能的最长回文子序列为 "bbbb" 。
         * 
         * 输入：s = "cbbd"
         * 输出：2
         * 解释：一个可能的最长回文子序列为 "bb" 。
         * 
         * dp[i][j]，从i->j之间的最长回文子序列的长度
         * 
        */
        /* 
            时间：O(n ^ 2)，记忆化递归，会计算每个字母组合一次，一共n^2个字母组合，所以是n^2，类比动态规划的复杂度；
            没有记忆化，每个组合都会遍历多次，就是2 ^ n
            空间：O(n ^ 2)
        */
        // 记忆化递归
        var longestPalindromeSubseq = function(s) {
            const memo = new Array(s.length).fill(0).map(() => new Array(s.length).fill(-1))
            const helper = (i, j) => {
                if (i > j) {
                    return 0
                } 
                if (i === j) {
                    return 1
                }
                if (memo[i][j] !== -1) {
                    return memo[i][j]
                }
                if (s[i] === s[j]) {
                    memo[i][j] = helper(i + 1, j - 1) + 2
                } else {
                    memo[i][j] = Math.max(helper(i + 1, j), helper(i, j - 1))
                }
                return memo[i][j]
            }
            return helper(0, s.length - 1)
        };
        console.log(longestPalindromeSubseq('abc'));
        console.log(longestPalindromeSubseq('aaa'));
    </script>
</body>

</html>